- Title
- Sufficient conditions for graphs to be maximally 4-restricted edge connected
- Creator
- Wang, Mujiangshan; Lin, Yuqing; Wang, Shiying; Wang, Miyu
- Relation
- Australasian Journal of Combinatorics Vol. 70, Issue 1, p. 123-136
- Relation
- https://ajc.maths.uq.edu.au/?page=get_volumes&volume=70
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2018
- Description
- For a subset S of edges in a connected graph G, the set S is a k-restricted edge cut if G − S is disconnected and every component of G − S has at least k vertices. The k-restricted edge connectivity of G, denoted by λk(G), is defined as the cardinality of a minimum k-restricted edge cut. A connected graph G is said to be λk-connected if G has a k-restricted edge cut. Let ξk(G) = min{|[X, ̅X ]| : |X| = k, G[X] is connected}, where ̅X = V (G)X. A graph G is said to be maximally k-restricted edge connected if λk(G) = ξk(G). In this paper we show that if G is a λ₄-connected graph with λ₄(G) ≤ ξ₄(G) and the girth satisfies g(G) ≥ 8, and there do not exist six vertices u₁, u₂, u₃, v₁, v₂ and v₃ in G such that the distance d(ui, vj) ≥ 3, (1 ≤ i, j ≤ 3), then G is maximally 4-restricted edge connected.
- Subject
- graphs; mathematics; simple graphs; finite graphs; undirected graphs
- Identifier
- http://hdl.handle.net/1959.13/1390109
- Identifier
- uon:33000
- Identifier
- ISSN:1034-4942
- Language
- eng
- Full Text
- Reviewed
- Hits: 7387
- Visitors: 3455
- Downloads: 372
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 143 KB | Adobe Acrobat PDF | View Details Download |